package 找树左下角的值;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 找树左下角的值
 *  解法;层次遍历,如果从右往左更简单
 * @date 2022/11/3 12:27
 */
public class Demo513 {

      //Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
    //层次遍历
    public int findBottomLeftValue(TreeNode root) {
          List<List<Integer>> res=new ArrayList<>();
            if(root==null){
               return 0;
           }
         Queue<TreeNode> queue=new LinkedList<>();
           queue.add(root);
           while (!queue.isEmpty()){
               int size=queue.size();
               List<Integer> temp=new ArrayList<>();
               while (size-->0){
                   TreeNode poll = queue.poll();
                   temp.add(poll.val);
                   if(poll.left!=null){
                       queue.add(poll.left);
                   }
                   if(poll.right!=null){
                       queue.add(poll.right);
                   }
               }
               res.add(temp);
           }
          return res.get(res.size()-1).get(0);
    }

}
